package Solution;

import sun.reflect.generics.tree.Tree;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

    }


    TreeNode smallNumNode = null;
    public TreeNode Convert(TreeNode root) {
        if (root == null) {
            return null;
        }
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    public TreeNode convert(TreeNode root) {
        if (root == null) {
            return null;
        }

        convert(root.left);

        root.left = smallNumNode;
        if (smallNumNode != null) {
            smallNumNode.right = root;
        }
        smallNumNode = root;

        convert(root.right);
        return root;
    }


    public int[] smallestK (int[] arr, int k) {
        int[] ret = new int[k];
        if (k == 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer> (new Comparator<Integer>() {
            public int compare (Integer a, Integer b) {
                return b - a;
            }
        });
        int i = 0;
        while (i < k) {
            priorityQueue.offer(arr[i]);
            i++;
        }
        while (i < arr.length && !priorityQueue.isEmpty()) {
            if (priorityQueue.peek() > arr[i]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
            i++;
        }
        i = 0;
        while (i < k) {
            ret[i] = priorityQueue.poll();
            i++;
        }
        return ret;
    }
}

